The invention relates generally to the field of digital computer systems, and more particularly to systems and method for performing fast Fourier transforms (FFT""s) in parallel on a digital computer system comprising a plurality of processors.
The Fourier transform is used in many applications, including, for example, seismic signal analysis and signal processing. A Fourier transform of a sequence of, for example, spatial or temporal data, in which the data identifies the amplitude of a signal as a function of space or time, transforms the data into the frequency domain. The transformed data identifies the amplitudes of various frequencies which, when signals of those frequencies are added together, would correspond to the original data signal, and thus identifies the spectral components of the original data signal and the amplitude of each of those components in the original data signal. The spectral information can be processed, using an inverse Fourier transform, to regenerate the original data signal. A Fourier transform can be useful in, for example, removing high- and/or low-frequency noise from a data signal, since the data signal can be transformed to the spectral domain, low- and/or high-frequency components removed, and an inverse Fourier transform applied to the remaining components to generate a filtered data signal which does not contain the removed frequency components. In addition, a Fourier transform can be used in generating a time- or frequency-scaled version of the data signal, as well as the convolution of, or correlation between, two data signals.
Generation of a Fourier transform on a digital computer can be accelerated by use of one of several so-called xe2x80x9cFFTxe2x80x9d (xe2x80x9cfast Fourier transformxe2x80x9d) algorithms popularized by J. W. Coolly and J. W. Tukey, as described in, for example, W. Press, Numerical Algorithms in Fortran (1992: Cambridge University Press), chapter 12. Often the time required to generate a Fourier transform, and the data storage requirements therefor, can be reduced by using so-called xe2x80x9creal-to-complexxe2x80x9d (xe2x80x9crc-FFTxe2x80x9d) or xe2x80x9ccomplex-to-realxe2x80x9d (xe2x80x9ccr-FFTxe2x80x9d) FFT algorithms. Serial methodologies have been developed for performing an rc-FFT operation on, for example, a single processor in a computer or in a single process. However, it would be preferable to perform the rc-FFT operation on a plurality of processors in a like plurality of processes, or threads of a single process in parallel, to reduce the time required to perform the rc-FFT operation.
The invention provides a new and improved system and method for performing an FFT operation on a computer comprising a plurality of processors in parallel.
In brief summary, the invention provides a parallel FFT generating system for generating a FFT of an input vector. The parallel FFT generating system comprises a plurality of processes configured to receive the input vector and process the input vector in parallel in relation to a set of twiddle factors to generate an output vector, the output vector comprising a Fourier transform representation of the input vector.